1529C - Parsa's Humongous Tree - CodeForces Solution

// time-limit: 1000
// problem-url: https://codeforces.com/contest/1529/problem/C
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int MAXN=2e5;
vector<int> adj[MAXN];
vector<pair<ll,ll>> lim;
ll dp1[MAXN], dp2[MAXN];

void dfs(int u, int p) {
	auto [l,r]=lim[u];

	ll sum1=0,sum2=0;
	for (int v : adj[u]) {
		if (v==p) continue;
		auto [l2,r2]=lim[v];
		dfs(v,u);
		sum1+=max(dp1[v]+abs(l-l2),dp2[v]+abs(l-r2));
		sum2+=max(dp1[v]+abs(r-l2),dp2[v]+abs(r-r2));
	}

	dp1[u]=sum1;
	dp2[u]=sum2;
}

signed slv() {
	int n; cin >> n;
	lim.clear();
	for (int i = 0; i < n; i++) {
		ll l, r; cin >> l >> r;
		lim.push_back({l,r});
	}

	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; --u,--v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(0,0);
	cout << max(dp1[0],dp2[0]) << '\n';
	return 0;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--) slv();
	return 0;
}